package com.cqs.leetcode.string;

import java.util.HashMap;

/**
 * @author lixiaowen
 * @create 2019-12-15
 */
public class RegularExpressionMatching10 {

    private Boolean[][] status = null;

    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();
        status = new Boolean[sc.length][p.length()];
        return isMatch(sc,0, pc, 0);
    }



    private boolean isMatch(char[] sc, final int scur, char[] ps,final int pcur) {
        //终止条件
        if (pcur == ps.length) return sc.length == scur;
        if (scur >= sc.length) {
            int tmp = pcur;
            while (tmp + 1 < ps.length && ps[tmp + 1] == '*'){
                tmp += 2;//指针的移动2位
            }
            return tmp == ps.length;
        }
        Boolean matchStatus = status[scur][pcur];
        if (matchStatus != null) return matchStatus;
        //主需要处理当前字符
        boolean charMatch = (ps[pcur] == '.') || sc[scur] == ps[pcur];
        //有*号的情况
        if (pcur+1 < ps.length && ps[pcur + 1] == '*'){
            //有点不好理解:
           matchStatus = isMatch(sc, scur, ps, pcur + 2) || (charMatch && isMatch(sc, scur + 1, ps, pcur));
        }else {
            matchStatus = charMatch && isMatch(sc, scur + 1, ps, pcur+1);
        }
        status[scur][pcur] = matchStatus;
        return matchStatus;
    }

    public static void main(String[] args) {
        RegularExpressionMatching10 regular = new RegularExpressionMatching10();
        String source = "mississippi";
        String pattern = "mis*is*ip*.";
//        source = "pp";
//        pattern = "p*";
//        source = "aab";
//        pattern = "c*a*b*";
        source="";
        pattern=".*";
        source = "acaabbaccbbacaabbbb";
        source = "acaabbaccbbacaabbbb";
        pattern= "a*.*b*.*a*aa*a*";
        boolean match = regular.isMatch(source, pattern);
        System.out.println(source + "\t" + pattern + "\t" + match);
    }

}
